package leecode

func numTrees(n int) int {
	dp := make([]int, n+1)
	dp[0] = 1
	for i := 1; i <= n; i++ {
		for j := 1; j <= i; j++ {
			//dp[i] += dp[以j为头节点左子树节点数量]*dp[以j为头节点右子树的节点数量]
			//每个元素作为头节点时的结果
			dp[i] += dp[j-1] * dp[i-j]
		}
	}
	return dp[len(dp)-1]
}
